CMU 11611 的课程笔记。讲句法的相关概念，sentence parsing 的两大结构(Constituency structure and Dependency structure)，以及Chomsky Hierarchy。

Syntax

句法(syntax) 具体来说就是把单词安排在一起的方法，前面我们其实已经涉猎了一些句法知识，如 POS, ngram 等，这一章将介绍相对更复杂的概念。

Syntax is NOT Morphology:

形态学以单词为单位，处理的是单词内部的结构；而句法处理多个单词的各种组合，单位是词组和句子
形态学通常是不规则的；而句法通常是规则的，不规则占小比例，大多数情况下句法由全局的一般规则组成。

Syntax is NOT Semantics:

语义是关于句子的含义；句法是关于句子的结构本身
一个句子在句法结构上可以是 well-formed，然而语义上非常糟糕
E.g. Colorless green ideas sleep furiously
一些比较有名的语言学理论尝试从句法表达中“读取”语义表达

Constituency(组成性)

基本思想： 单词的组合可以具有像一个单独的单位或短语那样的功能，这样的单词组合称为成分(constituent)，我们可以通过成分的集合来观察句子结构。

constituent: a group of words that “go together” (or relate more closely to one another than to other words in the sentence). We can view the structure of a sentence as a collection of nested constituents

可以从几个角度来识别成分：

Distribution:
一个成分可以是一个能放在句子不同位置的单位(unit)

E.g. John talked [to the children] [about drugs].
     John talked [about drugs] [to the children].

Substituion/expansion/pro-forms:
可以被替换/扩充的一些 unit，比如说一些状语
```
E.g. I sat [on the box/right on top of the box/there]
```
Coordination/regular internal sturcture/no intrusion/fragments/semantics…

最简单粗暴的方法就是理解为 词组(phrase)，多个单词组成的成分就是词组(phrase)，一个词组可以内嵌多个词组

E.g.
Noun Phrases
• **The elephant** arrived.
• **The big ugly elephant** arrived.
Prepositional Phrases(also contains a noun phrase)
• I arrived **on ***Tuesday*** **.
• I arrived **under the ***leaking roof*** **.

Grammatical relation(语法关系)

语法关系(grammatical relation) 是传统语法关于主语(SUBJECTS)和宾语(OBJECTS)的思想的形式化，在之后讨论一致关系(agreement)中再具体介绍语法关系，这里先有个印象。

关于主语，我们有下面三种认定事实：

主语是句子中的第一个名词短语
主语是句子中的动作发出者(actor)
主语是 what the sentence is about

所有这些都是对的，但没有一个 always right。

E.g.
– Oswald shot Kennedy
– Kennedy was shot by Oswald – Oswald was shot by Ruby
– Who shot Oswald?
• Active/Passive
– Oswald shot Kennedy
– Kennedy was shot by Oswald
• Relative clauses
– Oswald who shot Kennedy was shot by Ruby
– Kennedy who Oswald shot didn't shoot anybody
• Syntactic (not semantic)
– The batter hit the ball. [subject is semantic agent]
– The ball was hit by the batter. [subject is semantic patient]
– The ball was given a whack by the batter. [subject is semantic recipient]
– {George, the key, the wind} opened the door.
• Subject ≠ topic
– I just married the most beautiful woman in the world.
– Now beans, I like.
– As for democracy, I think it’s the best form of government.
• English subjects
– agree with the verb
– when pronouns, in nominative case (I/she/he vs. me/her/him)
– omitted from infinitive clauses (I tried __ to read the book, I hoped __ to be chosen)
• English objects
– when pronouns, in accusative case
– become subjects in passive sentences

Subcategorization and dependency(次范畴化和依存关系)

次范畴化和依存关系(subcategorization and dependency) 涉及到单词和短语之间的某些类别的关系，如动词 want 后可以接不定式(I want to fly to Detroit) 或名词短语(I want a flight to Detroit)，这种事实称为动词的次范畴(subcategorization)，也是之后再讨论。

Two views of linguistic structure

Constituency (phrase structure)

Phrase structure organizes words into nested constituents. It’s represented by trees generated by a context-free grammar. An important construct is the constituent (complete sub-tree).

通常由上下文无关语法 产生，重要的组成是成分。一种 bottom-up 的理解是，对一个句子的所有单词进行词性标注，然后根据一定的规则，一步步将其合并为“更大”的成分(产生子树)，直到组成一个句子。

Dependency structure

Dependency structure shows which words depend on (modify or are arguments of) which other words. The basic unit is a binary relation between words called a dependency

依存结构(Dependency structure) 两个主要构成部分是 head 和 dependents

head:

提供了主要含义(main meaning)的单词
“this smart student of linguistics with long hair”
这个例子中的 head 是 student，而不是 hair 之类的东西
提供了最重要的屈折特征(inflectional features)的单词
Inflection includes things like tense, number, and gender

来看一些 Dependency structure 的作用，一个从句子产生的角度来看，可以通过 head 确定名词词组(noun phrase)的单复数，以此来决定后面动词的单复数。看下面的例子，只有 “teacher/teachers” 这个 head 决定了 noun phrase 是单数还是复数，“class/classes”，“child/children” 并没有什么用。

Singular Plural
• The teacher blinks
• The short teacher blinks
• The teacher of the class blinks
• The teacher of the classes blinks
• The children’s teacher blinks
• The child’s teacher blinks
• The teachers blink
• The short teachers blink
• The teachers of the class blink
• The teachers of the classes blink
• The children’s teachers blink
• The child’s teachers blink

另一个应用是 QA 系统，如下，要回答 Who won an award? 这个问题，可能会有两个答案，student 或者 Alan，然而看 dependency parse tree 可以发现，student 和 won 之间有直接的联系(direct link)，所以结果当然是 student won an award

Chomsky Hierarchy

Formal Grammar

一个形式语法(formal grammar) G 定义了一个 formal language，用 L(G)来表示，包括以下部分：

N: a set of non-terminal symbols
$\Sigma$: a set of terminal symbols
R: a set of production rules of the form $(\Sigma \cup N)^* N(\Sigma \cup N)^* \rightarrow (\Sigma \cup N)^* $
$S \in N$: a distinguished/special start symbol

一些术语

Grammatical: a sentence in the language
Ungrammatical: a sentence not in the language
Derivation: sequence of top-down production steps
Parse tree: graphical representation of the derivation
A string is grammatical iff there exists a derivation for it.

Chomsky Hierarchy

Chomsky 根据 production rule 的形式，把形式语法分为4类：

0型语法(type 0 grammar)：重写规则为 φ → ψ，并且要求 φ 不是 empty string。
上下文有关语法(context-sensitive grammar)：重写规则为 φ1Aφ2 → φ1ωφ2，在上下文 φ1-φ2 中，单个的 non-terminal 符号 A 被重写为符号串 ω，所以，这种语法对上下文敏感，是上下文有关的。上下文有关语法又叫做 1型语法。
上下文无关语法(context-free grammar)：重写规则为A → ω，左边是一个 non-terminal 符号，右边是一个或多个 terminal 和 non-terminal 符号。当 A 重写为 ω 时，没有上下文的限制，所以，这种语法对上下文自由，是上下文无关的。上下文无关语法又叫做 2型语法。把上下文无关语法应用于自然语言的形式分析中，就形成了“短语结构语法”(phrase structure grammar)
有限状态语法/正则语法(finite state grammar/regular grammar)：重写规则为 A→aQ 或 A→a。左边必须是一个 non-terminal 符号，右边可以是一个 empty string，或者是一个 terminal 符号，又或者是一个 terminal 符号跟一个 non-terminal 符号，只有这三种情况。如果把 A 和 Q 看成不同的状态，那么，由重写规则可知，由状态 A 转入状态 Q 时，可生成一个终极符号 a，因此，这种语法叫做有限状态语法。有限状态语法又叫做 3型语法。

每一个有限状态语法的都是上下文无关的，每一个上下文无关语法都是上下文有关的，而每一个上下文有关语法都是0型的，Chomsky把由0型语法生成的语言叫0型语言，把由上下文有关语法、上下文无关语法、有限状态语法生成的语言分别叫做上下文有关语言、上下文无关语言、有限状态语言。有限状态语言包含于上下文无关语言之中，上下文无关语言包含于上下文有关语言之中，上下文有关语言包含于0型语言之中。这样就形成了语法的“Chomsky层级”（Chomsky hierarchy）。在自然语言处理中,我们最感兴趣的是上下文无关语法和上下文无关语言,它们是短语结构语法理论的主要研究对象。

Pumping Lemma for Regular Languages

An intuition (from Jurafsky & MarEn, p. 533): “…if a regular language has any long strings (longer than the number of states in the automaton), there must be some sort of loop in the automaton for the language. We can use this fact by showing that if a language doesn’t have such a loop, then it can’t be regular.”

如果一个 RL 有任何长字符串（比自动机中的状态数更长），在该语言的自动机中必定有某种循环。我们可以使用这个事实表明，如果一种语言没有这样的循环，那么它不能是 regular 的。

由此可见英语是 regular language

1
2
3

L1 = (the cat|dog|mouse|...)* (chased|bit|ate|...)* likes tuna fish
L2 = English
L1 ∩ L2 = (the cat|dog|mouse|...)^n (chased|bit|ate|...)^(n-1) likes tuna fish

语法的Chomsky层级